package leetcode.D100.T79;

class Solution {
    // 一刷
    /*private final static int[] dx = {0, 0, -1, 1};
    private final static int[] dy = {-1, 1, 0, 0};
    private boolean flag = false;
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board.length == 0 ? 0 : board[0].length;
        boolean[][] used = new boolean[m][n];
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(board[i][j] == word.charAt(0)) {
                    dfs(board, word, i, j, used, 0);
                    if(flag) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private void dfs(char[][] board, String word, int x, int y, boolean[][] used, int suc) {
        int m = board.length, n = board.length == 0 ? 0 : board[0].length;
        suc++;
        used[x][y] = true;
        if(suc == word.length()) {
            flag = true;
            return;
        }
        for(int i=0; i<4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= m || ny < 0 || ny >= n || used[nx][ny] ||board[nx][ny] != word.charAt(suc)) {
                continue;
            }
            dfs(board, word, nx, ny, used, suc);
            if(flag) {
                return;
            }
        }
        used[x][y] = false;
    }*/

    // 二刷
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};
    private boolean flag = false;
    public boolean exist(char[][] board, String word) {
        boolean[][] used = new boolean[board.length][board[0].length];
        for (int i=0; i<board.length; ++i) {
            for (int j=0; j<board[0].length; ++j) {
                dfs(board, word, i, j, 0, used);
                if (flag)
                    return true;
            }
        }
        return false;
    }

    private void dfs(char[][] board, String word, int x, int y, int cur, boolean[][] used) {
        if (word.charAt(cur) != board[x][y])
            return;
        if (cur == word.length()-1) {
            flag = true;
            return;
        }
        used[x][y] = true;
        int m = board.length, n = board[0].length;
        for (int i=0; i<4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= m || ny >= n || used[nx][ny])
                continue;
            dfs(board, word, nx, ny, cur+1, used);
            if (flag)
                return;
        }
        used[x][y] = false;
    }
}
